package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/20 9:26
 */
public class C28 {

    public static int kmp(String str1, String str2) {
        return -1;
    }

    public static int[] getNextArray(char[] str) {
        int N = str.length;
        int[] next = new int[N];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < N) {
            if (str[i - 1] == str[cn]) {        // 如果它等于前边一个元素, 则它失败跳到前边一个元素
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }


    // for test
    public static void main(String[] args) {
        int[] nextArray = getNextArray("aaabaab".toCharArray());
        System.out.println(Arrays.toString(nextArray));
    }

}
